package 贪心;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 最多可以参加的会议数目.java
 * @Description TODO
 * @createTime 2020年10月23日 15:03:00
 * 给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。
 *
 * 你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。
 *
 * 请你返回你可以参加的 最大 会议数目。
 * 输入：events = [[1,2],[2,3],[3,4]]
 * 输出：3
 * 解释：你可以参加所有的三个会议。
 * 安排会议的一种方案如上图。
 * 第 1 天参加第一个会议。
 * 第 2 天参加第二个会议。
 * 第 3 天参加第三个会议。
 * 示例 2：
 *
 * 输入：events= [[1,2],[2,3],[3,4],[1,2]]
 * 输出：4
 * 示例 3：
 *
 * 输入：events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
 * 输出：4
 * 示例 4：
 *
 * 输入：events = [[1,100000]]
 * 输出：1
 * 示例 5：
 *
 * 输入：events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
 * 输出：7
 *
 *
 * 从每个区间中选中一个数 后面不可以重复使用 最多可以有多少个数字
 * 贪心就是 排序+记录 每步最优得整体最优
 * 体现的是怎么选
 * 按照第一个元素升序排序 然后根据两个元素的差进行排序
*/
public class 最多可以参加的会议数目 {
    public static void main(String[] args) {
        int[][] events={{1,2},{1,2},{3,3},{1,5},{1,5}};

        Arrays.sort(events, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                int temp=o1[1]-o1[0];
                int map=o2[1]-o2[0];
                return o1[0]==o2[0]?temp-map:o1[0]-o2[0];
            }
        });

        System.out.println(Arrays.deepToString(events));


        int temp=1,count=0;

        for (int i=0;i<events.length;i++) {
            if(events[i][0]<=temp&&events[i][1]>=temp){
            temp++;
            count++;
            continue;
            }
            if(temp>events[i][1]){
                continue;
            }
            while (!(events[i][0]<=temp&&events[i][1]>=temp)){
                temp++;
            }
            count++;

        }


        System.out.println(count);



    }

    /*
    * class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, new Comparator<int[]>(){
            @Override
            public int compare(int[] a, int[] b){
                return a[0] - b[0];
            }
        });
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        int day = 0, id = 0, n = events.length, res = 0;
        while(id < n || !queue.isEmpty()){
            if(queue.isEmpty()){
                queue.add(events[id][1]);
                day = events[id++][0];
            }
            while(id < n && events[id][0] <= day){
                queue.add(events[id++][1]);
            }
            if(queue.peek() >= day){
                day++;
                res++;
            }
            queue.poll();
        }
        return res;
    }
}
*/
}
